package 变长滑动窗口2

import (
	"math"
)

func shortestBeautifulSubstring(s string, k int) string {
	cnt := 0
	left := 0
	minLen := math.MaxInt
	ans := ""
	for i, str := range s {
		if str == '1' {
			cnt++
		}
		for cnt >= k {
			currentLen := i - left + 1 // 当前窗口长度

			// 1. 找到更短的有效子串，直接更新
			if currentLen < minLen {
				minLen = currentLen
				ans = s[left : i+1] // 切片语法：[start:end)，end需+1才包含right位置
			} else if currentLen == minLen {
				// 2. 长度相同时，取字典序更小的子串
				currentSub := s[left : i+1]
				if ans == "" || currentSub < ans {
					ans = currentSub
				}
			}
			if s[left] == '1' {
				cnt--
			}
			left++

		}
	}
	return ans
}

//package main
//
//import "strings"
//
//// shortestBeautifulSubstring 寻找字符串s中包含至少k个'1'的最短子串
//// 若存在多个长度相同的子串，返回字典序最小的那个；若不存在则返回空字符串
//func shortestBeautifulSubstring(s string, k int) string {
//    // 先检查字符串中'1'的总数是否小于k，若不足则直接返回空（不可能存在符合条件的子串）
//    if strings.Count(s, "1") < k {
//        return ""
//    }
//
//    // 初始化结果为整个字符串（最坏情况，后续会被更短的子串替换）
//    ans := s
//    cnt1 := 0          // 记录当前窗口中'1'的数量
//    left := 0          // 滑动窗口的左边界，窗口范围为[left, right]
//
//    // 右指针遍历字符串，扩展窗口
//    for right, b := range s {
//        // 计算当前字符是否为'1'：'1'的ASCII码末位为1，'0'为0，用b&1快速判断
//        // 若为'1'则cnt1加1，否则不变
//        cnt1 += int(b & 1)
//
//        // 收缩窗口的核心逻辑：
//        // 1. 当窗口中'1'的数量超过k时，需要左移左边界减少'1'的数量
//        // 2. 当左边界是'0'时，移除它不影响'1'的数量，但能缩短窗口长度，因此也需要左移
//        for cnt1 > k || s[left] == '0' {
//            // 左边界字符离开窗口，若为'1'则cnt1减1
//            cnt1 -= int(s[left] & 1)
//            left++ // 左指针右移，缩小窗口
//        }
//
//        // 当窗口中正好包含k个'1'时，判断是否为更优解
//        if cnt1 == k {
//            // 当前窗口对应的子串（[left, right]闭区间）
//            currentSub := s[left : right+1]
//
//            // 比较规则：
//            // 1. 长度更短时，直接更新结果
//            // 2. 长度相同时，选择字典序更小的子串（字符串直接比较在Go中是字典序比较）
//            if len(currentSub) < len(ans) || (len(currentSub) == len(ans) && currentSub < ans) {
//                ans = currentSub
//            }
//        }
//    }
//
//    return ans
//}
